package subject_set.newcoder;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

/**
 * @author haomin
 * @date 2023/01/15 18:44
 **/
public class NC2 {
    public class Solution {
        public void reorderList(ListNode head) {
            if(head == null) return;
            ListNode fast = head;
            ListNode slow = head;
            while(fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode pre = slow.next;
            if(pre != null && pre.next != null) {
                ListNode next = pre.next;
                while(next != null) {
                    pre.next = next.next;
                    next.next = slow.next;
                    slow.next = next;
                    next = pre.next;
                }
            }
            merge(head, slow);
        }
        public void merge(ListNode head, ListNode slow) {
            ListNode p = head;
            ListNode q = slow.next;
            while(q != null && p != null) {
                slow.next = q.next;
                q.next = p.next;
                p.next = q;
                q = slow.next;
                p = p.next.next;
            }
        }
    }
}